1. Field of the Invention
The present invention relates to a flash memory and a method for controlling the same, and more particularly to a flash memory and a method for controlling the same, enabling the writing and reading of data by the block unit while efficiently managing the mapping between logic and physical addresses of a block.
This application is based on Korean Application No. KPA 1999-41835, which is incorporated herein for all purposes.
2. Description of the Prior Art
A flash memory developed by the INTEL corporation co., Ltd. for the first time in the early 1980s is a kind of the EPROM, but different from the general EPROM in that the flash memory does not need separate hardware for a program and data in the flash memory can be deleted and written with software.
Due to the volatile and programmable characteristics of the flash memory, the flash memory is widely used in a built-in type system such as a mobile phone or other mobile devices like a personal digital assistant (PDA).
The flash memory allows an arbitrary access to data stored at a particular location like the existing RAM or other volatile storage devices, magnetic discs, and the like, but uses a different method for correcting and deleting data.
That is, in the case of deleting data written in a certain block of an initialized flash memory, an entire unit in which the block is included is deleted.
Here, bytes having physically consecutive addresses are referred to as a block which is used as a basic unit for operations with respect to the flash memory. Further, a unit constituted with plural blocks in the flash memory is physically deleted at one time as a basic unit for a delete operation.
Accordingly, data is mainly accessed by the block unit in the flash memory as in a disc, rather than reading and writing data by the byte unit as in the RAM.
Software that enables the flash memory to be used as a block device is generally referred to as a flash translation layer (FTL).
TrueFFS [FTL97] of the M-system company and FlashFX [FX99] of the Datalight company may be referred to as the typical FTL products.
Particularly, a component, out of various components of the above software, for supporting a block re-mapping is referred to as FTL in the TrueFFS [FX99] and as VBX in the FlashFX, and the FTL of the M-System company is selected as a PC Card standard storing format.
In the case in which the flash memory is accessed by the block unit, the flash memory is divided into blocks each having a certain size smaller than a unit.
A number sequentially assigned to a divided block is referred to as a physical block number (PBN), and an imaginary number of a divided block which a user has in mind is referred to as a logical block number (LBN).
A method for providing a mapping between the logical block number (LBN) and the physical block number (PBN) is mainly classified into a fixed mapping and an arbitrary mapping.
The fixed mapping is a method for fixedly defining a relation between the logical block number (LBN) and the physical block number (PBN).
In a very simple case in which a separate header is not used, the relation may be indicated as LBN=PBN.
FIG. 1(A) is a view for explaining a general fixed mapping, and FIG. 2 is a block diagram for showing peripheral circuits together with a general flash memory. As shown in FIG. 1(A) and FIG. 2, if data written in block 2 of a unit of a flash memory 2 is to be updated, data of blocks 1, 3, and 4 are first read to be written in a RAM 3, all the data of a unit to which the blocks 1, 2, 3, and 4 belong are deleted, the data of the blocks 1, 3, and 4 written in the RAM 3 are read to be again written in the blocks 1, 3, and 4, and new data is written in the block 2.
Accordingly, it takes a long time to delete and re-write block data. Furthermore, data in the blocks 1, 2, 3, and 4 may be completely lost if a failure occurs just after deleting block data.
That is, the fixed mapping has an advantage that it does not need storage space and an algorithm for maintaining complicated mapping information, and a code size is small. However, fixed mapping has a disadvantage in that performance of a delete operation or an update operation is not good.
The arbitrary mapping is mainly used in the existing FTL products, and is characterized in that a relation between the logical block number (LBN) and the physical block number (PBN) is not fixedly defined.
That is, an arbitrary logical block is allocated to an empty physical block, so that the relation may be indicated as MAP (LBN)=PBN.
Mapping information between a logical unit number (LUN) and a physical unit number (PUN) is stored in the RAM 3 and a flash memory 2 together with mapping information between the logical block number (LBN) and the physical block number (PBN).
The mapping information between the physical unit number (PUN) and the logical unit number (LUN) is written in a map table in the RAM 3 to be used in transforming a logical address to a physical address, so that, if a mapping relation is changed due to a delete operation, an update operation, or a retrieve operation, the map table is also updated to continuously allow an access to the logical address.
FIG. 1(B) is a view for explaining a general arbitrary mapping. As shown in FIG. 1(B), in the case in which a central processing unit 1 performs a read operation, the logical block number (LBN) requested by a user is transformed into the physical block number (PBN) through the map table.
As for a write operation, like the read operation described above, the logical block number (LBN) is first transformed into the physical block number (PBN) for an access to a corresponding block. At this time, if data is written in the corresponding block in advance, data of a unit to which the block belongs is completely deleted due to the property of the flash memory, data of a block not to be updated and data of a block to be updated are re-written in the deleted unit or in a new unit, and then the previous unit is indicated to be deleted.
At this time, the physical block number (PBN) with respect to the logical block number (LBN) is updated in the map table.
Further, since a rate of using a memory becomes low if many blocks are not used in a unit, only used blocks are moved to a different unit, wherein a logical number is assigned to the unit and then transformed into a physical block so that access to the same logical unit number (LUN) can be performed even though data of a unit is moved.
As stated above, a conventional arbitrary mapping method used for a flash memory writes and reads data in and from the flash memory using a map table.
Accordingly, the conventional arbitrary method used for the flash memory has drawbacks in that it needs a separate storage space for maintaining mapping information required to transform a logical address to an arbitrary physical address, requires a long time for writing or updating data, and has difficulties in embodying or implementing a complicated mapping structure or an algorithm with errors.
Accordingly, in order to solve the problem, it is an object of the present invention to provide a flash memory and a method for controlling the same, enabling the writing and reading of data by the block unit while efficiently managing the mapping between logical and physical addresses of a block.
In order to achieve the above object, a flash memory according to the present invention comprises units, each of which includes a plurality of data blocks for writing data; a plurality of spare blocks emptied for writing updated data of the data blocks; a map block for designating an actual location in which data is written; and a header block for recording flash memory information and unit information.
Further, in order to achieve the above object, in a flash memory having units, each of which includes a plurality of data blocks for writing data, a plurality of spare blocks emptied for writing updated data of the data blocks, a map block for designating an actual location in which data is written, and a header block for recording flash memory information and unit information, the method for controlling the flash memory according to the present invention comprises steps of searching a logical unit to which a logical block belongs; searching a physical unit with respect to the logical unit; and searching a physical block location with respect to the logical block in the map block of the physical unit, to thereby control a mapping operation.
Accordingly, the present invention, in the case of updating data of a data block, first writes update data into an empty spare block in the same unit, updates mapping information of the map block, and updates state information of a previous block, so that a user can have access to data by using the same address and there is no need of deleting a unit every time the block is updated. Therefore, the present invention enhances an efficiency of writing and updating data by reducing the number of delete times.